{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#1.0",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "class city_map(object):\n",
    "    def __init__(self,size=[10,10],pop_sum=100):\n",
    "        self.size=size\n",
    "        self.pop_set=np.zeros([pop_sum,4])\n",
    "        for i in range(pop_sum):\n",
    "            self.pop_set[i,0]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,1]=np.random.rand()*size[1]\n",
    "            self.pop_set[i,2]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,3]=np.random.rand()*size[1]\n",
    "            self.lines=[]\n",
    "            self.line_plot=[]\n",
    "            self.d_lines=[]\n",
    "            self.sample=0.5\n",
    "    def show_map(self,save_name=0):\n",
    "        fig = plt.figure(figsize=(10,10))\n",
    "        for i in range(len(self.pop_set)):\n",
    "            plt.scatter(self.pop_set[i,0],self.pop_set[i,1],alpha=0.3,color=\"red\")\n",
    "            plt.scatter(self.pop_set[i,2],self.pop_set[i,3],alpha=0.3,color=\"red\")\n",
    "            if len(self.lines)>0:\n",
    "                if self.d_lines[i]==\"not_pass\":\n",
    "                    plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "                else:\n",
    "                    plt.plot([self.pop_set[i,0],self.d_lines[i][0][0]],[self.pop_set[i,1],self.d_lines[i][0][1]],alpha=0.1,color=\"blue\")\n",
    "                    #plt.plot([self.d_lines[i][0][0],self.d_lines[i][1][0]],[self.d_lines[i][0][1],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "                    plt.plot([self.pop_set[i,2],self.d_lines[i][1][0]],[self.pop_set[i,3],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "            else:\n",
    "                plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "        if len(self.lines)>0:\n",
    "            for i in range(len(self.line_plot)-1):\n",
    "                plt.plot([self.line_plot[i][0],self.line_plot[i][2]],[self.line_plot[i][1],self.line_plot[i][3]],alpha=0.5,color=\"black\")\n",
    "            plt.plot([self.line_plot[-1][0],self.line_plot[-1][2]],[self.line_plot[-1][1],self.line_plot[-1][3]],alpha=0.5,color=\"green\")\n",
    "            for i in range(len(self.lines)-1):\n",
    "                plt.scatter(self.lines[i][0],self.lines[i][1],alpha=1,color=\"black\")\n",
    "            plt.scatter(self.lines[-1][0],self.lines[-1][1],color=\"green\",alpha=0.5)\n",
    "        plt.savefig(\"D:/3_bodies/pic/sub_\"+str(save_name)+\".jpg\")\n",
    "        plt.show()\n",
    "        return 0\n",
    "    def set_line(self,from_point,to_point):\n",
    "        rate=((from_point[0]-to_point[0])**2+(from_point[1]-to_point[1])**2)**0.5\n",
    "        if from_point[0]-to_point[0]==0:\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "            x_line=from_point[0]*np.ones(len(y_line))\n",
    "        elif from_point[1]-to_point[1]==0:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=from_point[1]*np.ones(len(x_line))\n",
    "        else:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "        print(x_line)\n",
    "        for i in range(len(x_line)):\n",
    "            self.lines.append([x_line[i],y_line[i]])\n",
    "        return 0\n",
    "    def distance(self,point):\n",
    "        d_min=self.size[0]+self.size[1]+100\n",
    "        n_point=[0,0]\n",
    "        for l_point in self.lines:\n",
    "            d=(l_point[0]-point[0])**2+(l_point[1]-point[1])**2\n",
    "            if d<d_min:\n",
    "                d_min=d\n",
    "                n_point=l_point\n",
    "        return d_min,n_point\n",
    "        \n",
    "    def reward(self):\n",
    "        r=0\n",
    "        self.d_lines=[]\n",
    "        for i in range(len(self.pop_set)):\n",
    "            d1,point1=self.distance([self.pop_set[i,0],self.pop_set[i,1]])\n",
    "            d2,point2=self.distance([self.pop_set[i,2],self.pop_set[i,3]])\n",
    "            if d1+d2<(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2:\n",
    "                self.d_lines.append([point1,point2])\n",
    "                r+=d1+d2\n",
    "            else:\n",
    "                self.d_lines.append(\"not_pass\")\n",
    "                r+=(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2\n",
    "        return r/len(self.pop_set)\n",
    "    def ran_run(self,line_num=1,times=100):\n",
    "        \n",
    "        r_line=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(line_num):\n",
    "                self.set_line(np.random.rand(2)*self.size[0],np.random.rand(2)*self.size[0])\n",
    "            r_line.append(self.reward())\n",
    "            print(r_line[-1])\n",
    "            self.show_map()\n",
    "        return np.mean(r_line)\n",
    "    def ran_run_step(self,step_num=[5,2],step_l=0.5,times=20):\n",
    "        r_min=\"start\"\n",
    "        output=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(step_num[1]):\n",
    "                start_point=[int(np.random.rand()*self.size[0]),int(np.random.rand()*self.size[1])]\n",
    "                self.set_line(start_point,[start_point[0]+step_num[0]+0.1,start_point[1]])\n",
    "            r=self.reward()\n",
    "            #print(r)\n",
    "            if r_min==\"start\":\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            elif r_min>r:\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                del(self.line_plot[-1])\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            #self.show_map()\n",
    "        return output\n",
    "    def find_best(self,step_num=[5,1],end_time=1000,step_l=0.5,amp=1):\n",
    "        self.show_map(save_name=\"raw\")\n",
    "        self.lines=self.ran_run_step(step_num=step_num,times=20)\n",
    "        r=self.reward()+len(self.lines)*amp\n",
    "        print(self.reward())\n",
    "        self.show_map(save_name=\"start\")\n",
    "        for time in range(end_time):\n",
    "            while True:\n",
    "                root=np.random.randint(0,len(self.lines))\n",
    "                if not (([self.lines[root][0]+step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0]-step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0],self.lines[root][1]+step_l] in self.lines) and ([self.lines[root][0],self.lines[root][1]-step_l] in self.lines)):\n",
    "                    break\n",
    "            go_on=True\n",
    "            while go_on:\n",
    "                if np.random.rand()<0.5:\n",
    "                    if np.random.rand()<0.5 and [self.lines[root][0]+step_l,self.lines[root][1]] not in self.lines:\n",
    "                        go_on=False\n",
    "                        self.lines.append([self.lines[root][0]+step_l,self.lines[root][1]])\n",
    "                        self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0]+step_l,self.lines[root][1]])\n",
    "                    elif [self.lines[root][0]-step_l,self.lines[root][1]] not in self.lines:\n",
    "                        go_on=False\n",
    "                        self.lines.append([self.lines[root][0]-step_l,self.lines[root][1]])\n",
    "                        self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0]-step_l,self.lines[root][1]])\n",
    "                else:\n",
    "                    if np.random.rand()<0.5 and [self.lines[root][0],self.lines[root][1]+step_l] not in self.lines:\n",
    "                        go_on=False\n",
    "                        self.lines.append([self.lines[root][0],self.lines[root][1]+step_l])\n",
    "                        self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0],self.lines[root][1]+step_l])\n",
    "                    elif [self.lines[root][0],self.lines[root][1]-step_l] not in self.lines:\n",
    "                        go_on=False\n",
    "                        self.lines.append([self.lines[root][0],self.lines[root][1]-step_l])\n",
    "                        self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0],self.lines[root][1]-step_l])\n",
    "            \n",
    "            #print(self.lines)\n",
    "            r_temp=self.reward()+len(self.lines)*amp\n",
    "            self.show_map(save_name=time)\n",
    "            if self.reward()+len(self.lines)*amp<r:\n",
    "                r=r_temp\n",
    "            else:\n",
    "                del(self.lines[-1])\n",
    "                del(self.line_plot[-1])\n",
    "        print(self.reward())\n",
    "        self.show_map()\n",
    "        return 0\n",
    "c_map=city_map()\n",
    "#c_map.set_line([5.01,0],[5,10])\n",
    "#c_map.set_line([0,10],[10,0])\n",
    "#print(c_map.reward())\n",
    "\n",
    "#c_map.ran_run_step(step_num=[5,1])\n",
    "#c_map.show_map()\n",
    "c_map.find_best(step_num=[1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#video generator",
    "import os\n",
    "import cv2\n",
    "from PIL import Image\n",
    "fourcc = cv2.VideoWriter_fourcc('X', 'V', 'I', 'D') \n",
    "path=r\"D:/3_bodies/pic/sub_\"#input(\"path?\")\n",
    "save_path=r\"D:/3_bodies/Sub_order_n_0-1.mp4\"#input(\"save_path?\")\n",
    "post_video=cv2.VideoWriter(save_path, fourcc, 3,(720,720))\n",
    "for i in range(10):\n",
    "    img=cv2.imread(path+\"raw\"+\".jpg\")\n",
    "    post_video.write(img)\n",
    "for i in range(10):\n",
    "    img=cv2.imread(path+\"start\"+\".jpg\")\n",
    "    post_video.write(img)\n",
    "for i in range(183):\n",
    "    print(path+str(i)+\".jpg\")\n",
    "    img=cv2.imread(path+str(i)+\".jpg\")\n",
    "    post_video.write(img)\n",
    "    del img\n",
    "    #if filename==\"0.jpg\":\n",
    "        #Image.fromarray(img).show()\n",
    "\n",
    "post_video.release()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#lightning\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "class city_map(object):\n",
    "    def __init__(self,size=[10,10],from_point=[5,9],pop_sum=100):\n",
    "        self.size=size\n",
    "        self.from_point=from_point\n",
    "        self.pop_set=np.zeros([pop_sum,4])\n",
    "        for i in range(pop_sum):\n",
    "            self.pop_set[i,0]=np.random.rand()+from_point[0]-0.5\n",
    "            self.pop_set[i,1]=np.random.rand()+from_point[1]-0.5\n",
    "            self.pop_set[i,2]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,3]=0\n",
    "            self.lines=[]\n",
    "            self.line_plot=[]\n",
    "            self.d_lines=[]\n",
    "            self.sample=0.5\n",
    "    def show_map(self):\n",
    "        fig = plt.figure(figsize=(10,10))\n",
    "        for i in range(len(self.pop_set)):\n",
    "            plt.scatter(self.pop_set[i,0],self.pop_set[i,1],alpha=0.3,color=\"red\")\n",
    "            plt.scatter(self.pop_set[i,2],self.pop_set[i,3],alpha=0.3,color=\"red\")\n",
    "            if self.d_lines[i]==\"not_pass\":\n",
    "                plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "            else:\n",
    "                plt.plot([self.pop_set[i,0],self.d_lines[i][0][0]],[self.pop_set[i,1],self.d_lines[i][0][1]],alpha=0.1,color=\"blue\")\n",
    "                #plt.plot([self.d_lines[i][0][0],self.d_lines[i][1][0]],[self.d_lines[i][0][1],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "                plt.plot([self.pop_set[i,2],self.d_lines[i][1][0]],[self.pop_set[i,3],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "            for i in range(len(self.line_plot)):\n",
    "                plt.plot([self.line_plot[i][0],self.line_plot[i][2]],[self.line_plot[i][1],self.line_plot[i][3]],alpha=0.5,color=\"black\")\n",
    "        for i in range(len(self.lines)):\n",
    "            plt.scatter(self.lines[i][0],self.lines[i][1],alpha=1,color=\"black\")\n",
    "        plt.show()\n",
    "        return 0\n",
    "    def set_line(self,from_point,to_point):\n",
    "        rate=((from_point[0]-to_point[0])**2+(from_point[1]-to_point[1])**2)**0.5\n",
    "        x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "        y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "        for i in range(len(x_line)):\n",
    "            self.lines.append([x_line[i],y_line[i]])\n",
    "        return 0\n",
    "    def distance(self,point):\n",
    "        d_min=self.size[0]+self.size[1]+100\n",
    "        n_point=[0,0]\n",
    "        for l_point in self.lines:\n",
    "            d=(l_point[0]-point[0])**2+(l_point[1]-point[1])**2\n",
    "            if d<d_min:\n",
    "                d_min=d\n",
    "                n_point=l_point\n",
    "        return d_min,n_point\n",
    "        \n",
    "    def reward(self):\n",
    "        r=0\n",
    "        self.d_lines=[]\n",
    "        for i in range(len(self.pop_set)):\n",
    "            d1,point1=self.distance([self.pop_set[i,0],self.pop_set[i,1]])\n",
    "            d2,point2=self.distance([self.pop_set[i,2],self.pop_set[i,3]])\n",
    "            if d1+d2<(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2:\n",
    "                self.d_lines.append([point1,point2])\n",
    "                r+=d1+d2\n",
    "            else:\n",
    "                self.d_lines.append(\"not_pass\")\n",
    "                r+=(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2\n",
    "        return r/len(self.pop_set)\n",
    "    def ran_run(self,line_num=1,times=100):\n",
    "        \n",
    "        r_line=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(line_num):\n",
    "                self.set_line(np.random.rand(2)*self.size[0],np.random.rand(2)*self.size[0])\n",
    "            r_line.append(self.reward())\n",
    "            print(r_line[-1])\n",
    "            self.show_map()\n",
    "        return np.mean(r_line)\n",
    "    def ran_run_step(self,step_num=[5,2],times=20):\n",
    "        r_min=\"start\"\n",
    "        output=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(step_num[1]):\n",
    "                start_point=np.random.rand(2)*self.size[0]\n",
    "                self.set_line(start_point,[start_point[0]+step_num[0],start_point[1]+0.01])\n",
    "            r=self.reward()\n",
    "            #print(r)\n",
    "            if r_min==\"start\":\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]+0.01])\n",
    "            elif r_min>r:\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                del(self.line_plot[-1])\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]+0.01])\n",
    "            #self.show_map()\n",
    "        return output\n",
    "    def find_best(self,step_num=[5,1],end_time=5000,step_l=0.2,amp=0.1):\n",
    "        self.lines=[self.from_point]\n",
    "        r=self.reward()+len(self.lines)*amp\n",
    "        print(self.reward())\n",
    "        self.show_map()\n",
    "        for time in range(end_time):\n",
    "            root=np.random.randint(0,len(self.lines))\n",
    "            if np.random.rand()<0.5:\n",
    "                if np.random.rand()<0.5:\n",
    "                    self.lines.append([self.lines[root][0]+step_l,self.lines[root][1]])\n",
    "                    self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0]+step_l,self.lines[root][1]])\n",
    "                else:\n",
    "                    self.lines.append([self.lines[root][0]-step_l,self.lines[root][1]])\n",
    "                    self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0]-step_l,self.lines[root][1]])\n",
    "            else:\n",
    "                if np.random.rand()<0.5:\n",
    "                    self.lines.append([self.lines[root][0],self.lines[root][1]+step_l])\n",
    "                    self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0],self.lines[root][1]+step_l])\n",
    "                else:\n",
    "                    self.lines.append([self.lines[root][0],self.lines[root][1]-step_l])\n",
    "                    self.line_plot.append([self.lines[root][0],self.lines[root][1],self.lines[root][0],self.lines[root][1]-step_l])\n",
    "            if self.reward()+len(self.lines)*amp<r:\n",
    "                r=self.reward()+len(self.lines)*amp\n",
    "            else:\n",
    "                del(self.lines[-1])\n",
    "                del(self.line_plot[-1])\n",
    "        print(self.reward())\n",
    "        self.show_map()\n",
    "        return 0\n",
    "c_map=city_map()\n",
    "#c_map.set_line([5.01,0],[5,10])\n",
    "#c_map.set_line([0,10],[10,0])\n",
    "#print(c_map.reward())\n",
    "\n",
    "#c_map.ran_run_step(step_num=[5,1])\n",
    "#c_map.show_map()\n",
    "c_map.find_best()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#2.0  greedy\n",
    "import numpy as np\n",
    "import copy\n",
    "import matplotlib.pyplot as plt\n",
    "class city_map(object):\n",
    "    def __init__(self,size=[10,10],pop_sum=100):\n",
    "        self.size=size\n",
    "        self.pop_set=np.zeros([pop_sum,4])\n",
    "        for i in range(pop_sum):\n",
    "            self.pop_set[i,0]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,1]=np.random.rand()*size[1]\n",
    "            self.pop_set[i,2]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,3]=np.random.rand()*size[1]\n",
    "            self.lines=[]\n",
    "            self.line_plot=[]\n",
    "            self.d_lines=[]\n",
    "            self.sample=0.5\n",
    "    def show_map(self,save_name=0):\n",
    "        fig = plt.figure(figsize=(10,10))\n",
    "        for i in range(len(self.pop_set)):\n",
    "            plt.scatter(self.pop_set[i,0],self.pop_set[i,1],alpha=0.3,color=\"red\")\n",
    "            plt.scatter(self.pop_set[i,2],self.pop_set[i,3],alpha=0.3,color=\"red\")\n",
    "            if len(self.lines)>0:\n",
    "                if self.d_lines[i]==\"not_pass\":\n",
    "                    plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "                else:\n",
    "                    plt.plot([self.pop_set[i,0],self.d_lines[i][0][0]],[self.pop_set[i,1],self.d_lines[i][0][1]],alpha=0.1,color=\"blue\")\n",
    "                    #plt.plot([self.d_lines[i][0][0],self.d_lines[i][1][0]],[self.d_lines[i][0][1],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "                    plt.plot([self.pop_set[i,2],self.d_lines[i][1][0]],[self.pop_set[i,3],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "            else:\n",
    "                plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "        if len(self.lines)>0:\n",
    "            for i in range(len(self.line_plot)-1):\n",
    "                plt.plot([self.line_plot[i][0],self.line_plot[i][2]],[self.line_plot[i][1],self.line_plot[i][3]],alpha=0.5,color=\"black\")\n",
    "            plt.plot([self.line_plot[-1][0],self.line_plot[-1][2]],[self.line_plot[-1][1],self.line_plot[-1][3]],alpha=0.5,color=\"green\")\n",
    "            for i in range(len(self.lines)-1):\n",
    "                plt.scatter(self.lines[i][0],self.lines[i][1],alpha=1,color=\"black\")\n",
    "            plt.scatter(self.lines[-1][0],self.lines[-1][1],color=\"green\",alpha=0.5)\n",
    "        plt.savefig(\"D:/3_bodies/pic/sub_\"+str(save_name)+\".jpg\")\n",
    "        plt.show()\n",
    "        return 0\n",
    "    def set_line(self,from_point,to_point):\n",
    "        rate=((from_point[0]-to_point[0])**2+(from_point[1]-to_point[1])**2)**0.5\n",
    "        if from_point[0]-to_point[0]==0:\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "            x_line=from_point[0]*np.ones(len(y_line))\n",
    "        elif from_point[1]-to_point[1]==0:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=from_point[1]*np.ones(len(x_line))\n",
    "        else:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "        print(x_line)\n",
    "        for i in range(len(x_line)):\n",
    "            self.lines.append([x_line[i],y_line[i]])\n",
    "        return 0\n",
    "    def distance(self,point):\n",
    "        d_min=self.size[0]+self.size[1]+100\n",
    "        n_point=[0,0]\n",
    "        for l_point in self.lines:\n",
    "            d=(l_point[0]-point[0])**2+(l_point[1]-point[1])**2\n",
    "            if d<d_min:\n",
    "                d_min=d\n",
    "                n_point=l_point\n",
    "        return d_min,n_point\n",
    "        \n",
    "    def reward(self):\n",
    "        r=0\n",
    "        self.d_lines=[]\n",
    "        for i in range(len(self.pop_set)):\n",
    "            d1,point1=self.distance([self.pop_set[i,0],self.pop_set[i,1]])\n",
    "            d2,point2=self.distance([self.pop_set[i,2],self.pop_set[i,3]])\n",
    "            if d1+d2<(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2:\n",
    "                self.d_lines.append([point1,point2])\n",
    "                r+=d1+d2\n",
    "            else:\n",
    "                self.d_lines.append(\"not_pass\")\n",
    "                r+=(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2\n",
    "        return r/len(self.pop_set)\n",
    "    def ran_run(self,line_num=1,times=100):\n",
    "        \n",
    "        r_line=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(line_num):\n",
    "                self.set_line(np.random.rand(2)*self.size[0],np.random.rand(2)*self.size[0])\n",
    "            r_line.append(self.reward())\n",
    "            print(r_line[-1])\n",
    "            self.show_map()\n",
    "        return np.mean(r_line)\n",
    "    def ran_run_step(self,step_num=[5,2],step_l=0.5,times=20):\n",
    "        r_min=\"start\"\n",
    "        output=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(step_num[1]):\n",
    "                start_point=[int(np.random.rand()*self.size[0]),int(np.random.rand()*self.size[1])]\n",
    "                self.set_line(start_point,[start_point[0]+step_num[0]+0.1,start_point[1]])\n",
    "            r=self.reward()\n",
    "            #print(r)\n",
    "            if r_min==\"start\":\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            elif r_min>r:\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                del(self.line_plot[-1])\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            #self.show_map()\n",
    "        return output\n",
    "    def get_near(self,step_l=0.5):\n",
    "        self.near_group=[]\n",
    "        for i in range(len(self.lines)):\n",
    "            for j in [1,-1]:\n",
    "                if [self.lines[i][0]+step_l*j,self.lines[i][1]] not in self.lines:\n",
    "                    self.near_group.append([self.lines[i],[self.lines[i][0]+step_l*j,self.lines[i][1]]])\n",
    "                if [self.lines[i][0],self.lines[i][1]+step_l*j] not in self.lines:\n",
    "                    self.near_group.append([self.lines[i],[self.lines[i][0],self.lines[i][1]+step_l*j]])\n",
    "        return 0\n",
    "    def find_best(self,step_num=[5,1],end_time=1000,step_l=0.5,amp=0.01):\n",
    "        self.show_map(save_name=\"raw\")\n",
    "        self.lines=self.ran_run_step(step_num=step_num,times=20)\n",
    "        r=self.reward()+len(self.lines)*amp\n",
    "        #print(self.reward())\n",
    "        self.show_map(save_name=\"start\")\n",
    "        for time in range(end_time):\n",
    "            while True:\n",
    "                root=np.random.randint(0,len(self.lines))\n",
    "                if not (([self.lines[root][0]+step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0]-step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0],self.lines[root][1]+step_l] in self.lines) and ([self.lines[root][0],self.lines[root][1]-step_l] in self.lines)):\n",
    "                    break\n",
    "            self.get_near(step_l=step_l)\n",
    "            r_min_temp=r\n",
    "            aim_near=None\n",
    "            for i in range(len(self.near_group)):\n",
    "                self.lines.append(self.near_group[i][1])\n",
    "                r_temp=self.reward()+len(self.lines)*amp\n",
    "                if r_temp<r_min_temp:\n",
    "                    r_min_temp=copy.deepcopy(r_temp)\n",
    "                    aim_near=copy.deepcopy(i)\n",
    "                del(self.lines[-1])\n",
    "            if aim_near!=None:\n",
    "                self.lines.append(self.near_group[aim_near][1])  \n",
    "                self.line_plot.append([self.near_group[aim_near][0][0],self.near_group[aim_near][0][1],self.near_group[aim_near][1][0],self.near_group[aim_near][1][1]])\n",
    "            else:\n",
    "                print(\"end!\")\n",
    "                break\n",
    "            r=self.reward()+len(self.lines)*amp\n",
    "            self.show_map(save_name=time)\n",
    "        print(self.reward())\n",
    "        return 0\n",
    "c_map=city_map()\n",
    "#c_map.set_line([5.01,0],[5,10])\n",
    "#c_map.set_line([0,10],[10,0])\n",
    "#print(c_map.reward())\n",
    "\n",
    "#c_map.ran_run_step(step_num=[5,1])\n",
    "#c_map.show_map()\n",
    "c_map.find_best(step_num=[1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#2.2 greedy\n",
    "#changable  unfinished!!!\n",
    "import numpy as np\n",
    "import copy\n",
    "import matplotlib.pyplot as plt\n",
    "class city_map(object):\n",
    "    def __init__(self,size=[10,10],pop_sum=100):\n",
    "        self.size=size\n",
    "        self.pop_set=np.zeros([pop_sum,4])\n",
    "        for i in range(pop_sum):\n",
    "            self.pop_set[i,0]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,1]=np.random.rand()*size[1]\n",
    "            self.pop_set[i,2]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,3]=np.random.rand()*size[1]\n",
    "            self.lines=[]\n",
    "            self.line_plot=[]\n",
    "            self.d_lines=[]\n",
    "            self.sample=0.5\n",
    "    def change_pop(self,change_num=10):\n",
    "        for index in range(change_num):\n",
    "            i=int(np.random.rand()*len(self.pop_set))\n",
    "            self.pop_set[i,0]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,1]=np.random.rand()*size[1]\n",
    "            self.pop_set[i,2]=np.random.rand()*size[0]\n",
    "            self.pop_set[i,3]=np.random.rand()*size[1]\n",
    "        return change_num\n",
    "    def show_map(self,save_name=0):\n",
    "        fig = plt.figure(figsize=(10,10))\n",
    "        for i in range(len(self.pop_set)):\n",
    "            plt.scatter(self.pop_set[i,0],self.pop_set[i,1],alpha=0.3,color=\"red\")\n",
    "            plt.scatter(self.pop_set[i,2],self.pop_set[i,3],alpha=0.3,color=\"red\")\n",
    "            if len(self.lines)>0:\n",
    "                if self.d_lines[i]==\"not_pass\":\n",
    "                    plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "                else:\n",
    "                    plt.plot([self.pop_set[i,0],self.d_lines[i][0][0]],[self.pop_set[i,1],self.d_lines[i][0][1]],alpha=0.1,color=\"blue\")\n",
    "                    #plt.plot([self.d_lines[i][0][0],self.d_lines[i][1][0]],[self.d_lines[i][0][1],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "                    plt.plot([self.pop_set[i,2],self.d_lines[i][1][0]],[self.pop_set[i,3],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "            else:\n",
    "                plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "        if len(self.lines)>0:\n",
    "            for i in range(len(self.line_plot)-1):\n",
    "                plt.plot([self.line_plot[i][0],self.line_plot[i][2]],[self.line_plot[i][1],self.line_plot[i][3]],alpha=0.5,color=\"black\")\n",
    "            plt.plot([self.line_plot[-1][0],self.line_plot[-1][2]],[self.line_plot[-1][1],self.line_plot[-1][3]],alpha=0.5,color=\"green\")\n",
    "            for i in range(len(self.lines)-1):\n",
    "                plt.scatter(self.lines[i][0],self.lines[i][1],alpha=1,color=\"black\")\n",
    "            plt.scatter(self.lines[-1][0],self.lines[-1][1],color=\"green\",alpha=0.5)\n",
    "        plt.savefig(\"D:/3_bodies/pic/sub_\"+str(save_name)+\".jpg\")\n",
    "        plt.show()\n",
    "        return 0\n",
    "    def set_line(self,from_point,to_point):\n",
    "        rate=((from_point[0]-to_point[0])**2+(from_point[1]-to_point[1])**2)**0.5\n",
    "        if from_point[0]-to_point[0]==0:\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "            x_line=from_point[0]*np.ones(len(y_line))\n",
    "        elif from_point[1]-to_point[1]==0:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=from_point[1]*np.ones(len(x_line))\n",
    "        else:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "        print(x_line)\n",
    "        for i in range(len(x_line)):\n",
    "            self.lines.append([x_line[i],y_line[i]])\n",
    "        return 0\n",
    "    def distance(self,point):\n",
    "        d_min=self.size[0]+self.size[1]+100\n",
    "        n_point=[0,0]\n",
    "        for l_point in self.lines:\n",
    "            d=(l_point[0]-point[0])**2+(l_point[1]-point[1])**2\n",
    "            if d<d_min:\n",
    "                d_min=d\n",
    "                n_point=l_point\n",
    "        return d_min,n_point\n",
    "        \n",
    "    def reward(self):\n",
    "        r=0\n",
    "        self.d_lines=[]\n",
    "        for i in range(len(self.pop_set)):\n",
    "            d1,point1=self.distance([self.pop_set[i,0],self.pop_set[i,1]])\n",
    "            d2,point2=self.distance([self.pop_set[i,2],self.pop_set[i,3]])\n",
    "            if d1+d2<(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2:\n",
    "                self.d_lines.append([point1,point2])\n",
    "                r+=d1+d2\n",
    "            else:\n",
    "                self.d_lines.append(\"not_pass\")\n",
    "                r+=(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2\n",
    "        return r/len(self.pop_set)\n",
    "    def ran_run(self,line_num=1,times=100):\n",
    "        \n",
    "        r_line=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(line_num):\n",
    "                self.set_line(np.random.rand(2)*self.size[0],np.random.rand(2)*self.size[0])\n",
    "            r_line.append(self.reward())\n",
    "            print(r_line[-1])\n",
    "            self.show_map()\n",
    "        return np.mean(r_line)\n",
    "    def ran_run_step(self,step_num=[5,2],step_l=0.5,times=20):\n",
    "        r_min=\"start\"\n",
    "        output=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(step_num[1]):\n",
    "                start_point=[int(np.random.rand()*self.size[0]),int(np.random.rand()*self.size[1])]\n",
    "                self.set_line(start_point,[start_point[0]+step_num[0]+0.1,start_point[1]])\n",
    "            r=self.reward()\n",
    "            #print(r)\n",
    "            if r_min==\"start\":\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            elif r_min>r:\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                del(self.line_plot[-1])\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            #self.show_map()\n",
    "        return output\n",
    "    def get_near(self,step_l=0.5):\n",
    "        self.near_group=[]\n",
    "        for i in range(len(self.lines)):\n",
    "            for j in [1,-1]:\n",
    "                if [self.lines[i][0]+step_l*j,self.lines[i][1]] not in self.lines:\n",
    "                    self.near_group.append([self.lines[i],[self.lines[i][0]+step_l*j,self.lines[i][1]]])\n",
    "                if [self.lines[i][0],self.lines[i][1]+step_l*j] not in self.lines:\n",
    "                    self.near_group.append([self.lines[i],[self.lines[i][0],self.lines[i][1]+step_l*j]])\n",
    "        return 0\n",
    "    def ab_stat(self):\n",
    "        \n",
    "        for i in range(len(self.lines)):\n",
    "            \n",
    "    def find_best(self,step_num=[5,1],end_time=1000,step_l=0.5,amp=0.01):\n",
    "        self.show_map(save_name=\"raw\")\n",
    "        self.lines=self.ran_run_step(step_num=step_num,times=20)\n",
    "        r=self.reward()+len(self.lines)*amp\n",
    "        #print(self.reward())\n",
    "        self.show_map(save_name=\"start\")\n",
    "        for time in range(end_time):\n",
    "            while True:\n",
    "                root=np.random.randint(0,len(self.lines))\n",
    "                if not (([self.lines[root][0]+step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0]-step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0],self.lines[root][1]+step_l] in self.lines) and ([self.lines[root][0],self.lines[root][1]-step_l] in self.lines)):\n",
    "                    break\n",
    "            self.get_near(step_l=step_l)\n",
    "            r_min_temp=r\n",
    "            aim_near=None\n",
    "            for i in range(len(self.near_group)):\n",
    "                self.lines.append(self.near_group[i][1])\n",
    "                r_temp=self.reward()+len(self.lines)*amp\n",
    "                if r_temp<r_min_temp:\n",
    "                    r_min_temp=copy.deepcopy(r_temp)\n",
    "                    aim_near=copy.deepcopy(i)\n",
    "                del(self.lines[-1])\n",
    "            if aim_near!=None:\n",
    "                self.lines.append(self.near_group[aim_near][1])  \n",
    "                self.line_plot.append([self.near_group[aim_near][0][0],self.near_group[aim_near][0][1],self.near_group[aim_near][1][0],self.near_group[aim_near][1][1]])\n",
    "            else:\n",
    "                print(\"end!\")\n",
    "                break\n",
    "            r=self.reward()+len(self.lines)*amp\n",
    "            self.show_map(save_name=time)\n",
    "        print(self.reward())\n",
    "        return 0\n",
    "c_map=city_map()\n",
    "#c_map.set_line([5.01,0],[5,10])\n",
    "#c_map.set_line([0,10],[10,0])\n",
    "#print(c_map.reward())\n",
    "\n",
    "#c_map.ran_run_step(step_num=[5,1])\n",
    "#c_map.show_map()\n",
    "c_map.find_best(step_num=[1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#2.1 greedy\n",
    "#normal\n",
    "import numpy as np\n",
    "import copy\n",
    "import matplotlib.pyplot as plt\n",
    "class city_map(object):\n",
    "    def __init__(self,size=[10,10],pop_sum=100):\n",
    "        self.size=size\n",
    "        self.pop_set=np.zeros([pop_sum,4])\n",
    "        for i in range(pop_sum):\n",
    "            self.pop_set[i,0]=np.random.randn()*size[0]/3\n",
    "            self.pop_set[i,1]=np.random.randn()*size[1]/3\n",
    "            self.pop_set[i,2]=np.random.randn()*size[0]/3\n",
    "            self.pop_set[i,3]=np.random.randn()*size[1]/3\n",
    "            self.lines=[]\n",
    "            self.line_plot=[]\n",
    "            self.d_lines=[]\n",
    "            self.sample=0.5\n",
    "    def show_map(self,save_name=0):\n",
    "        fig = plt.figure(figsize=(10,10))\n",
    "        for i in range(len(self.pop_set)):\n",
    "            plt.scatter(self.pop_set[i,0],self.pop_set[i,1],alpha=0.3,color=\"red\")\n",
    "            plt.scatter(self.pop_set[i,2],self.pop_set[i,3],alpha=0.3,color=\"red\")\n",
    "            if len(self.lines)>0:\n",
    "                if self.d_lines[i]==\"not_pass\":\n",
    "                    plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "                else:\n",
    "                    plt.plot([self.pop_set[i,0],self.d_lines[i][0][0]],[self.pop_set[i,1],self.d_lines[i][0][1]],alpha=0.1,color=\"blue\")\n",
    "                    #plt.plot([self.d_lines[i][0][0],self.d_lines[i][1][0]],[self.d_lines[i][0][1],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "                    plt.plot([self.pop_set[i,2],self.d_lines[i][1][0]],[self.pop_set[i,3],self.d_lines[i][1][1]],alpha=0.1,color=\"blue\")\n",
    "            else:\n",
    "                plt.plot([self.pop_set[i,0],self.pop_set[i,2]],[self.pop_set[i,1],self.pop_set[i,3]],alpha=0.3,color=\"blue\")\n",
    "        if len(self.lines)>0:\n",
    "            for i in range(len(self.line_plot)-1):\n",
    "                plt.plot([self.line_plot[i][0],self.line_plot[i][2]],[self.line_plot[i][1],self.line_plot[i][3]],alpha=0.5,color=\"black\")\n",
    "            plt.plot([self.line_plot[-1][0],self.line_plot[-1][2]],[self.line_plot[-1][1],self.line_plot[-1][3]],alpha=0.5,color=\"green\")\n",
    "            for i in range(len(self.lines)-1):\n",
    "                plt.scatter(self.lines[i][0],self.lines[i][1],alpha=1,color=\"black\")\n",
    "            plt.scatter(self.lines[-1][0],self.lines[-1][1],color=\"green\",alpha=0.5)\n",
    "        plt.savefig(\"D:/3_bodies/pic/sub_\"+str(save_name)+\".jpg\")\n",
    "        plt.show()\n",
    "        return 0\n",
    "    def set_line(self,from_point,to_point):\n",
    "        rate=((from_point[0]-to_point[0])**2+(from_point[1]-to_point[1])**2)**0.5\n",
    "        if from_point[0]-to_point[0]==0:\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "            x_line=from_point[0]*np.ones(len(y_line))\n",
    "        elif from_point[1]-to_point[1]==0:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=from_point[1]*np.ones(len(x_line))\n",
    "        else:\n",
    "            x_line=np.arange(from_point[0],to_point[0],-self.sample*(from_point[0]-to_point[0])/rate)\n",
    "            y_line=np.arange(from_point[1],to_point[1],-self.sample*(from_point[1]-to_point[1])/rate)\n",
    "        print(x_line)\n",
    "        for i in range(len(x_line)):\n",
    "            self.lines.append([x_line[i],y_line[i]])\n",
    "        return 0\n",
    "    def distance(self,point):\n",
    "        d_min=self.size[0]+self.size[1]+100\n",
    "        n_point=[0,0]\n",
    "        for l_point in self.lines:\n",
    "            d=(l_point[0]-point[0])**2+(l_point[1]-point[1])**2\n",
    "            if d<d_min:\n",
    "                d_min=d\n",
    "                n_point=l_point\n",
    "        return d_min,n_point\n",
    "        \n",
    "    def reward(self):\n",
    "        r=0\n",
    "        self.d_lines=[]\n",
    "        for i in range(len(self.pop_set)):\n",
    "            d1,point1=self.distance([self.pop_set[i,0],self.pop_set[i,1]])\n",
    "            d2,point2=self.distance([self.pop_set[i,2],self.pop_set[i,3]])\n",
    "            if d1+d2<(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2:\n",
    "                self.d_lines.append([point1,point2])\n",
    "                r+=d1+d2\n",
    "            else:\n",
    "                self.d_lines.append(\"not_pass\")\n",
    "                r+=(self.pop_set[i,0]-self.pop_set[i,2])**2+(self.pop_set[i,1]-self.pop_set[i,3])**2\n",
    "        return r/len(self.pop_set)\n",
    "    def ran_run(self,line_num=1,times=100):\n",
    "        \n",
    "        r_line=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(line_num):\n",
    "                self.set_line(np.random.rand(2)*self.size[0],np.random.rand(2)*self.size[0])\n",
    "            r_line.append(self.reward())\n",
    "            print(r_line[-1])\n",
    "            self.show_map()\n",
    "        return np.mean(r_line)\n",
    "    def ran_run_step(self,step_num=[5,2],step_l=0.5,times=20):\n",
    "        r_min=\"start\"\n",
    "        output=[]\n",
    "        out_line=[]\n",
    "        for index in range(times):\n",
    "            self.lines=[]\n",
    "            for i in range(step_num[1]):\n",
    "                start_point=[int(np.random.rand()*self.size[0]),int(np.random.rand()*self.size[1])]\n",
    "                self.set_line(start_point,[start_point[0]+step_num[0]+0.1,start_point[1]])\n",
    "            r=self.reward()\n",
    "            #print(r)\n",
    "            if r_min==\"start\":\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            elif r_min>r:\n",
    "                r_min=r\n",
    "                output=self.lines\n",
    "                del(self.line_plot[-1])\n",
    "                self.line_plot.append([start_point[0],start_point[1],start_point[0]+step_num[0],start_point[1]])\n",
    "            #self.show_map()\n",
    "        return output\n",
    "    def get_near(self,step_l=0.5):\n",
    "        self.near_group=[]\n",
    "        for i in range(len(self.lines)):\n",
    "            for j in [1,-1]:\n",
    "                if [self.lines[i][0]+step_l*j,self.lines[i][1]] not in self.lines:\n",
    "                    self.near_group.append([self.lines[i],[self.lines[i][0]+step_l*j,self.lines[i][1]]])\n",
    "                if [self.lines[i][0],self.lines[i][1]+step_l*j] not in self.lines:\n",
    "                    self.near_group.append([self.lines[i],[self.lines[i][0],self.lines[i][1]+step_l*j]])\n",
    "        return 0\n",
    "    def find_best(self,step_num=[5,1],end_time=1000,step_l=0.5,amp=0.01):\n",
    "        self.show_map(save_name=\"raw\")\n",
    "        self.lines=self.ran_run_step(step_num=step_num,times=20)\n",
    "        r=self.reward()+len(self.lines)*amp\n",
    "        #print(self.reward())\n",
    "        self.show_map(save_name=\"start\")\n",
    "        for time in range(end_time):\n",
    "            while True:\n",
    "                root=np.random.randint(0,len(self.lines))\n",
    "                if not (([self.lines[root][0]+step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0]-step_l,self.lines[root][1]] in self.lines) and ([self.lines[root][0],self.lines[root][1]+step_l] in self.lines) and ([self.lines[root][0],self.lines[root][1]-step_l] in self.lines)):\n",
    "                    break\n",
    "            self.get_near(step_l=step_l)\n",
    "            r_min_temp=r\n",
    "            aim_near=None\n",
    "            for i in range(len(self.near_group)):\n",
    "                self.lines.append(self.near_group[i][1])\n",
    "                r_temp=self.reward()+len(self.lines)*amp\n",
    "                if r_temp<r_min_temp:\n",
    "                    r_min_temp=copy.deepcopy(r_temp)\n",
    "                    aim_near=copy.deepcopy(i)\n",
    "                del(self.lines[-1])\n",
    "            if aim_near!=None:\n",
    "                self.lines.append(self.near_group[aim_near][1])  \n",
    "                self.line_plot.append([self.near_group[aim_near][0][0],self.near_group[aim_near][0][1],self.near_group[aim_near][1][0],self.near_group[aim_near][1][1]])\n",
    "            else:\n",
    "                print(\"end!\")\n",
    "                break\n",
    "            r=self.reward()+len(self.lines)*amp\n",
    "            self.show_map(save_name=time)\n",
    "        print(self.reward())\n",
    "        return 0\n",
    "c_map=city_map()\n",
    "#c_map.set_line([5.01,0],[5,10])\n",
    "#c_map.set_line([0,10],[10,0])\n",
    "#print(c_map.reward())\n",
    "\n",
    "#c_map.ran_run_step(step_num=[5,1])\n",
    "#c_map.show_map()\n",
    "c_map.find_best(step_num=[1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
